package dfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author wcj
 * @Date 2021/7/6 20:02
 * @Version 1.0
 */
public class PathSumThird {

    private static List<List<Integer>> res;
    private static LinkedList<Integer> path;
    private static int sum;

    /**
     * 路径总和Ⅲ：不需要从根节点开始，也不需要到叶子节点结束，记录所有的路径
     * 深搜：
     * ①递归方法设计：dfs(TreeNode root,int target)参数同上
     * ②递归出口：root==null,截止；target==root.val
     * ③递归组合方式：前序遍历
     *
     * @param root
     * @param target
     * @return
     */
    public static List<List<Integer>> pathSum(TreeNode root, int target) {
        res = new ArrayList<>();
        path = new LinkedList<>();
        sum = target;
        dfsNode(root);
        return res;
    }

    public static void dfsNode(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root, sum);
        dfsNode(root.left);
        dfsNode(root.right);
    }

    public static void dfs(TreeNode root, int target) {
        if (root == null) {
            return;
        }

        // 不到叶子节点
        if (target == root.val) {
            path.add(root.val);
            res.add(new ArrayList<>(path));
            path.removeLast();
            return;
        }

        path.add(root.val);
        dfs(root.left, target - root.val);
        dfs(root.right, target - root.val);
        path.removeLast();
    }
}
